package com.algorithm;


import java.util.ArrayList;
import java.util.Arrays;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;

/**
 * <pre>
 * 分而治之 => D&C (Divide And Conquer)
 * 示例：把一个无序数组排序
 *
 * 分析：要使用D&C，因此需要将数组分解，知道满足基线条件。
 *
 * 快速排序的工作原理：
 *      首先，从数组中选择一个元素，这个元素被称为基准值（pivot）；
 *      接下来，找出比基准值小的元素以及比基准值大的元素；
 *      这被称为分区：
 *          ①一个由所有小于基准值的数字组成的子数组；
 *          ②基准值；
 *          ③一个由所有大于基准值的数字组成的子数组；
 *      再对两个子数组递归调用此排序函数，最后把数组拼接起来。
 *
 * 基线条件 =>> 为空或者只包含一个元素的数组是“有序”的
 * 递归条件 =>> 数组长度 > 1
 *
 * 注意：实现快速排序时，请随机地选择用作基准值的元素。
 *      快速排序的平均时间为：O（n log n）
 *      快速排序的最糟情况为：0(n²)
 * </pre>
 */
class QuickSort {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3, 5, 2, 1, 4};
        arr = quickSort(arr);
        System.out.println("快速排序后的数组为 =>> " + Arrays.toString(arr));
    }

    private static Integer[] quickSort(Integer[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        Integer pivot = arr[RandomUtil.randomInt(arr.length-1)];
        ArrayList<Integer> less = new ArrayList<Integer>();
        ArrayList<Integer> greater = new ArrayList<Integer>();
        for (Integer i : arr) {
            if (i < pivot) {
                less.add(i);
            }
            if (i > pivot) {
                greater.add(i);
            }
        }
        return ArrayUtil.addAll(quickSort(less.toArray(new Integer[0])), new Integer[]{pivot}, quickSort(greater.toArray(new Integer[0])));
    }

}